#include <bits/stdc++.h>

using namespace std;

// 矩阵中的最长递增路径
// 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度
// 对于每个单元格，你可以往上，下，左，右四个方向移动
// 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）
// 测试链接 : https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/

class Solution 
{
public:
    int m, n;

    int f1(vector<vector<int>>& matrix, int i, int j)
    {
        int next = 0;
        if(i > 0 && matrix[i][j] < matrix[i - 1][j])
            next = max(next, f1(matrix, i - 1, j));
        if(i + 1 < m && matrix[i][j] < matrix[i + 1][j])
            next = max(next, f1(matrix, i + 1, j));
        if(j > 0 && matrix[i][j] < matrix[i][j - 1])
            next = max(next, f1(matrix, i, j - 1));
        if(j + 1 < n && matrix[i][j] < matrix[i][j + 1])
            next = max(next, f1(matrix, i, j + 1));
        
        return next + 1;
    }

    int longestIncreasingPath1(vector<vector<int>>& matrix) 
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                ret = max(ret, f1(matrix, i, j));
            }
        }
        return ret;
    }

    int f2(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& dp)
    {
        if(dp[i][j] != -1) return dp[i][j];

        int next = 0;
        if(i > 0 && matrix[i][j] < matrix[i - 1][j])
            next = max(next, f2(matrix, i - 1, j, dp));
        if(i + 1 < m && matrix[i][j] < matrix[i + 1][j])
            next = max(next, f2(matrix, i + 1, j, dp));
        if(j > 0 && matrix[i][j] < matrix[i][j - 1])
            next = max(next, f2(matrix, i, j - 1, dp));
        if(j + 1 < n && matrix[i][j] < matrix[i][j + 1])
            next = max(next, f2(matrix, i, j + 1, dp));
        
        dp[i][j] = next + 1;
        return next + 1;
    }

    int longestIncreasingPath2(vector<vector<int>>& matrix) 
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                ret = max(ret, f2(matrix, i, j, dp));
            }
        }
        return ret;
    }
};


class Solution 
{
private:
    int m, n;
    int memo[201][201];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if(memo[i][j] != 0) return memo[i][j];

        int ret = 1;
        for(int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[i][j] < matrix[x][y])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                ret = max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }
};